#include <iostream>
#include <vector>
using namespace std;

// 96.31 %
class Solution
{
  private:
    int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int m, n;
    vector<vector<bool>> visited;
    bool inArea(int x, int y)
    {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    void dfs(vector<vector<char>> &grid, int x, int y)
    {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++)
        {
            int newx = x + d[i][0];
            int newy = y + d[i][1];
            if (inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1')
            {
                dfs(grid, newx, newy);
            }
        }
        return;
    }

  public:
    int numIslands(vector<vector<char>> &grid)
    {
        m = grid.size();
        if (m == 0)
            return 0;
        n = grid[0].size();
        int res = 0;
        visited = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (grid[i][j] == '1' && !visited[i][j])
                {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
};

int main()
{
    char arr[][5] = {
        {'1', '1', '1', '1', '0'},
        {'1', '1', '0', '1', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}};
    vector<vector<char>> myVector;

    for (int i = 0; i < 4; i++)
    {
        myVector.push_back({});
        for (int j = 0; j < 5; j++)
        {
            myVector[i].push_back(arr[i][j]);
        }
    }
    cout << Solution().numIslands(myVector) << endl;
    return 0;
    return 0;
}
